package company.tree;

import java.util.*;

import static java.util.Collections.emptyList;

/**
 * leetcode 236 变题
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：[3,5,1,6,2,0,8,null,null,7,4] [5,1]
 * 输出：3
 * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 * 示例 2：
 * <p>
 * <p>
 * 输入：[3,5,1,6,2,0,8,null,null,7,4], [5,4]
 * 输出：5
 * 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 * 示例 3：
 * <p>
 * 输入：root = [1,2], [1,2]
 * 输出：1
 *  
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [2, 105] 内。
 * -109 <= Node.val <= 109
 * 所有 Node.val 互不相同 。
 * p != q
 * p 和 q 均存在于给定的二叉树中。
 * 通过次数545,135提交次数781,899
 * <p>
 * 分析:
 * 1、分别落在左右节点，那么公共祖先就是最顶根节点
 * 2、分布在左树
 * 3、分布在右树
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class TreeCommonAncestorTwo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String[] split = input.split(" ");
        String[] treeNodes = split[0].replace("[", "").replace("]", "").replace(" ", "").split(",");
        String[] chirldNodes = split[1].replace("[", "").replace("]", "").replace(" ", "").split(",");
        List<String> nodeList = new ArrayList<>();
        for (int i = 0; i < chirldNodes.length; i++) {
            nodeList.add(chirldNodes[i]);
        }
        Deque<TreeNode> deque = new LinkedList<>();
        int index = 0;
        TreeNode treeNode = new TreeNode(Integer.parseInt(treeNodes[0]));
        deque.offer(treeNode);
        while (++index < treeNodes.length) {
            TreeNode poll = deque.poll();
            if (!"null".equals(treeNodes[index])) {
                TreeNode left = new TreeNode(Integer.parseInt(treeNodes[index]));
                poll.setLeft(left);
                deque.offer(left);
            }

            ++index;
            if (index < treeNodes.length && !"null".equals(treeNodes[index])) {
                TreeNode right = new TreeNode(Integer.parseInt(treeNodes[index]));
                poll.setRight(right);
                deque.offer(right);
            }
        }

        List<List<Integer>> allPath = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        lowestCommonAncestor(treeNode, allPath, path, nodeList);

        // 求交集
        List<Integer> list = allPath.stream().reduce((list1, list2) -> {
            list1.retainAll(list2);
            return list1;
        }).orElse(emptyList());
        System.out.println(list.get(list.size() - 1));
    }

    // 递归
    // 1、存在限制条件，当满足这个条件时，递归便不再继续。
    // 2、每次递归调用之后越来越接近这个限制条件。
    private static TreeNode lowestCommonAncestor(TreeNode root,
                                                 List<List<Integer>> allPath,
                                                 List<Integer> path, List<String> chirldNodes) {
        if (root == null) {
            return null;
        }

        // 记录路径
        if (chirldNodes.contains(root.getValue())) {
            path.add(root.getValue());
            allPath.add(new ArrayList<>(path));
            chirldNodes.remove(root.getValue());
            path.remove(root.getValue());
            return root;
        } else {
            path.add(root.getValue());
        }

        TreeNode left = lowestCommonAncestor(root.getLeft(), allPath, path, chirldNodes);
        TreeNode right = lowestCommonAncestor(root.getRight(), allPath, path, chirldNodes);

        if (left != null && right != null) {
            return root;
        }
        if (right == null) {
            return left;
        }
        if (left == null) {
            return right;
        }
        return root;
    }
}
